{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Distinct Difference Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: distinctDifferenceArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出不同元素数目差数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的数组 <code>nums</code> ，数组长度为 <code>n</code> 。</p>\n",
    "\n",
    "<p><code>nums</code> 的 <strong>不同元素数目差</strong> 数组可以用一个长度为 <code>n</code> 的数组 <code>diff</code> 表示，其中 <code>diff[i]</code> 等于前缀 <code>nums[0, ..., i]</code> 中不同元素的数目 <strong>减去</strong> 后缀 <code>nums[i + 1, ..., n - 1]</code> 中不同元素的数目。</p>\n",
    "\n",
    "<p>返回<em> </em><code>nums</code> 的 <strong>不同元素数目差</strong> 数组。</p>\n",
    "\n",
    "<p>注意 <code>nums[i, ..., j]</code> 表示 <code>nums</code> 的一个从下标 <code>i</code> 开始到下标 <code>j</code> 结束的子数组（包含下标 <code>i</code> 和 <code>j</code> 对应元素）。特别需要说明的是，如果 <code>i &gt; j</code> ，则 <code>nums[i, ..., j]</code> 表示一个空子数组。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,4,5]\n",
    "<strong>输出：</strong>[-3,-1,1,3,5]\n",
    "<strong>解释：\n",
    "</strong>对于 i = 0，前缀中有 1 个不同的元素，而在后缀中有 4 个不同的元素。因此，diff[0] = 1 - 4 = -3 。\n",
    "对于 i = 1，前缀中有 2 个不同的元素，而在后缀中有 3 个不同的元素。因此，diff[1] = 2 - 3 = -1 。\n",
    "对于 i = 2，前缀中有 3 个不同的元素，而在后缀中有 2 个不同的元素。因此，diff[2] = 3 - 2 = 1 。\n",
    "对于 i = 3，前缀中有 4 个不同的元素，而在后缀中有 1 个不同的元素。因此，diff[3] = 4 - 1 = 3 。\n",
    "对于 i = 4，前缀中有 5 个不同的元素，而在后缀中有 0 个不同的元素。因此，diff[4] = 5 - 0 = 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,2,3,4,2]\n",
    "<strong>输出：</strong>[-2,-1,0,2,3]\n",
    "<strong>解释：</strong>\n",
    "对于 i = 0，前缀中有 1 个不同的元素，而在后缀中有 3 个不同的元素。因此，diff[0] = 1 - 3 = -2 。\n",
    "对于 i = 1，前缀中有 2 个不同的元素，而在后缀中有 3 个不同的元素。因此，diff[1] = 2 - 3 = -1 。\n",
    "对于 i = 2，前缀中有 2 个不同的元素，而在后缀中有 2 个不同的元素。因此，diff[2] = 2 - 2 = 0 。\n",
    "对于 i = 3，前缀中有 3 个不同的元素，而在后缀中有 1 个不同的元素。因此，diff[3] = 3 - 1 = 2 。\n",
    "对于 i = 4，前缀中有 3 个不同的元素，而在后缀中有 0 个不同的元素。因此，diff[4] = 3 - 0 = 3 。 \n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n == nums.length&nbsp;&lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 50</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-distinct-difference-array](https://leetcode.cn/problems/find-the-distinct-difference-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-distinct-difference-array](https://leetcode.cn/problems/find-the-distinct-difference-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]', '[3,2,3,4,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, a: List[int]) -> List[int]:\n",
    "        n = len(a)\n",
    "        ans = [len(set(a[:i + 1])) - len(set(a[i + 1:])) for i in range(n)]\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        return [len(set(nums[:i+1]))-len(set(nums[i+1:])) for i in range(len(nums))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        diff = [0 for i in range(len(nums))]\n",
    "        ansset = set()\n",
    "        for i in range(len(nums)):\n",
    "            ansset.add(nums[i])\n",
    "            diff[i] = len(ansset)\n",
    "        ansset.clear()\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            diff[i] = diff[i] - len(ansset)\n",
    "            ansset.add(nums[i])\n",
    "        return diff\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from collections import Counter\n",
    "# class Solution:\n",
    "#     def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "#         cnt=Counter(nums)\n",
    "#         vis=set()\n",
    "#         ans=[]\n",
    "#         for num in nums:\n",
    "#             vis.add(num)\n",
    "#             cnt[num]-=1\n",
    "#             if cnt[num]==0:\n",
    "#                 del cnt[num]\n",
    "#             ans.append(len(vis)-len(cnt))\n",
    "#         return ans\n",
    "\n",
    "###灵茶山\n",
    "class Solution:\n",
    "\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        suf = [0] * (n + 1)\n",
    "\n",
    "        s = set()\n",
    "\n",
    "        for i in range(n - 1, 0, -1):\n",
    "\n",
    "            s.add(nums[i])\n",
    "\n",
    "            suf[i] = len(s)\n",
    "\n",
    "\n",
    "\n",
    "        s.clear()\n",
    "\n",
    "        ans = [0] * n\n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "\n",
    "            s.add(x)\n",
    "\n",
    "            ans[i] = len(s) - suf[i + 1]\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        f = []\n",
    "        for i in range(0,n):\n",
    "            a = 0\n",
    "            b = 0\n",
    "            d = []\n",
    "            e = []\n",
    "            for y in range(0,n):\n",
    "                m = nums[y]\n",
    "                if y <= i and m not in d:\n",
    "                    a += 1\n",
    "                    d.append(m)\n",
    "                elif y > i and m not in e:\n",
    "                    b += 1\n",
    "                    e.append(m)\n",
    "            c = a-b\n",
    "            f.append(c)\n",
    "        return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        n=[0]*len(nums)\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            n[i]=len(set(nums[:i+1]))-len(set(nums[i+1:]))\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        s = set()\n",
    "        pre = []\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in s:\n",
    "                s.add(nums[i])\n",
    "            pre.append(len(s))\n",
    "        s.clear()\n",
    "        last = [0 for i in range(len(nums)+1)]\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            if nums[i] not in s:\n",
    "                s.add(nums[i])\n",
    "            last[i] = len(s)\n",
    "        \n",
    "        ans = [0 for i in range(len(nums))]\n",
    "        for i in range(len(ans)):\n",
    "            ans[i] = pre[i] - last[i+1]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(1,len(nums)+1):\n",
    "            res.append( len(set(nums[:i])) -len(set(nums[i:])) )\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        for i in range(len(nums)):\n",
    "            res = len(set(nums[:i+1])) - len(set(nums[i+1:]))\n",
    "            ans.append(res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        res=[0]*n\n",
    "        a,b=[0]*51,[0]*51\n",
    "        for i in nums:\n",
    "            b[i]+=1\n",
    "            \n",
    "        for index,i in enumerate(nums):\n",
    "            b[i]-=1\n",
    "            a[i]+=1\n",
    "            aa,bb=0,0\n",
    "            for j,k in zip(a,b):\n",
    "                if j!=0:\n",
    "                    aa+=1\n",
    "                if k!=0:\n",
    "                    bb+=1\n",
    "            res[index]=aa-bb\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        s = set()\n",
    "        pre = []\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in s:\n",
    "                s.add(nums[i])\n",
    "            pre.append(len(s))\n",
    "        s.clear()\n",
    "        last = [0 for i in range(len(nums)+1)]\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            if nums[i] not in s:\n",
    "                s.add(nums[i])\n",
    "            last[i] = len(s)\n",
    "        \n",
    "        ans = [0 for i in range(len(nums))]\n",
    "        for i in range(len(ans)):\n",
    "            ans[i] = pre[i] - last[i+1]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        diff = []\n",
    "        for i in range(len(nums)):\n",
    "            diff.append(len(set(nums[0:i+1]))-len(set(nums[i+1:])))\n",
    "        return diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        return [len(set(nums[:i+1])) - len(set(nums[i+1:])) for i in range(len(nums))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        s = set()\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            s.add(nums[i])\n",
    "            suf[i] = len(s)\n",
    "\n",
    "        s.clear()\n",
    "        ans = [0] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            s.add(x)\n",
    "            ans[i] = len(s) - suf[i + 1]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        diff = []\n",
    "        for idx, num in enumerate(nums):\n",
    "            if idx == len(nums)-1:\n",
    "                list2 = []\n",
    "                list1 = nums\n",
    "            else:\n",
    "                list1 = nums[:idx+1]\n",
    "                list2 = nums[idx+1:]\n",
    "            diff.append(len(list(set(list1)))-len(list(set(list2))))\n",
    "        return diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "\n",
    "        for i in range(1,len(nums)+1):\n",
    "            if i < len(nums):\n",
    "                diff = len(set(nums[0:i])) - len(set(nums[i:]))\n",
    "                ans.append(diff)\n",
    "                \n",
    "            else:\n",
    "                diff = len(set(nums))\n",
    "                ans.append(diff)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        diff = [0 for i in range(len(nums))]\n",
    "        ansset = set()\n",
    "        for i in range(len(nums)):\n",
    "            ansset.add(nums[i])\n",
    "            diff[i] = len(ansset)\n",
    "        ansset.clear()\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            diff[i] = diff[i] - len(ansset)\n",
    "            ansset.add(nums[i])\n",
    "        return diff\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        len_nums = len(nums)\n",
    "        res = [0] * len_nums\n",
    "        b = [0] * (len_nums + 1)\n",
    "        set_a = set()\n",
    "        for i in range(len_nums - 1, 0, -1):\n",
    "            set_a.add(nums[i])\n",
    "            b[i] = len(set_a)\n",
    "        set_a.clear()\n",
    "        for i in range(len_nums):\n",
    "            set_a.add(nums[i])\n",
    "            res[i] = len(set_a) - b[i + 1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        for i in range(len(nums)):\n",
    "            res = len(set(nums[:i+1])) - len(set(nums[i+1:]))\n",
    "            ans.append(res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        s = set()\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            s.add(nums[i])\n",
    "            suf[i] = len(s)\n",
    "\n",
    "        s.clear()\n",
    "        ans = [0] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            s.add(x)\n",
    "            ans[i] = len(s) - suf[i + 1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        new_nums = []\n",
    "        length = len(nums)\n",
    "        for i in range(length):\n",
    "            new_nums.append(len(set(nums[0: i + 1])) - len(set(nums[i + 1: length])))\n",
    "        \n",
    "        return new_nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        return [(len(set(nums[:i + 1])) - len(set(nums[i + 1:]))) for i in range(len(nums))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        ret = []\n",
    "        for i in range(1, len(nums) + 1):\n",
    "            ret.append(len(set(nums[:i])) - len(set(nums[i:])))\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        cnt =defaultdict(int)\n",
    "        for x in nums:\n",
    "            cnt[x]+=1\n",
    "\n",
    "        ret = [0]*n\n",
    "        cnt2 = defaultdict(int)\n",
    "        for i,x in enumerate(nums):\n",
    "            cnt2[x]+=1\n",
    "            cnt[x]-=1\n",
    "            if cnt[x]==0:\n",
    "                del cnt[x]\n",
    "            ret[i] = len(cnt2) -len(cnt) \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        h = Counter(nums)\n",
    "        pre, suf = 0, len(h)\n",
    "        st = set()\n",
    "        res = []\n",
    "        for v in nums:\n",
    "            h[v] -= 1\n",
    "            if h[v] == 0:\n",
    "                suf -= 1\n",
    "                del h[v]\n",
    "            if v not in st:\n",
    "                pre += 1\n",
    "            st.add(v)\n",
    "            res.append(pre - suf)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        s=set()\n",
    "        n=len(nums)\n",
    "        pre=[0]*n\n",
    "        suf=[0]*(n+1)\n",
    "        for i,x in enumerate(nums) :\n",
    "            s.add(x)\n",
    "            pre[i]=len(s)\n",
    "        s.clear()\n",
    "        for i in range(n-1,-1,-1) :\n",
    "            s.add(nums[i])\n",
    "            suf[i]=len(s)\n",
    "        ans=[]\n",
    "        for i in range(n) :\n",
    "            ans.append(pre[i]-suf[i+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            ans.append(len(set(nums[:i+1])) - len(set(nums[i+1:])))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int] :\n",
    "        n = len(nums)\n",
    "        diff = []\n",
    "        for i in range(n) :\n",
    "            diff.append(len(set(nums[:i+1:])) - len(set(nums[i+1::])))\n",
    "        return diff\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        front = {}\n",
    "        back = {}\n",
    "        for n in nums:\n",
    "            back[n] = back.get(n, 0) + 1\n",
    "        diff = []\n",
    "        for n in nums:\n",
    "            front[n] = front.get(n, 0)+1\n",
    "            if back[n] == 1:\n",
    "                back.pop(n)\n",
    "            else:\n",
    "                back[n] = back[n] -1\n",
    "            diff.append(front.__len__() - back.__len__() )\n",
    "        return diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        prefix_count = [0] * n \n",
    "        suffix_count = [0] * n \n",
    "        diff = [0] * n \n",
    "        prefix_set = set()\n",
    "        suffix_set = set()\n",
    "        for i in range(n):\n",
    "            prefix_set.add(nums[i])\n",
    "            prefix_count[i] = len(prefix_set)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            suffix_set.add(nums[i])\n",
    "            suffix_count[i] = len(suffix_set)\n",
    "        \n",
    "        for i in range(n):\n",
    "            diff[i] = prefix_count[i] - suffix_count[i + 1] if (i + 1) < n else prefix_count[i]\n",
    "\n",
    "        return diff  \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        s = set()\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            s.add(nums[i])\n",
    "            suf[i] = len(s)\n",
    "\n",
    "        s.clear()\n",
    "        ans = [0] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            s.add(x)\n",
    "            ans[i] = len(s) - suf[i + 1]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        s = set()\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            s.add(nums[i])\n",
    "            suf[i] = len(s)\n",
    "\n",
    "        s.clear()\n",
    "        ans = [0] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            s.add(x)\n",
    "            ans[i] = len(s) - suf[i + 1]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "      pre_set, suf_set = set(), set()\n",
    "      pre_dif , suf_dif = [0]*len(nums), [0]*len(nums)\n",
    "      for i in range(len(nums)):\n",
    "        pre_set.add(nums[i])\n",
    "        pre_dif[i] = len(pre_set)\n",
    "      \n",
    "      for j in range(len(nums)-1, -1, -1):\n",
    "        suf_dif[j] = len(suf_set)\n",
    "        suf_set.add(nums[j])\n",
    "      \n",
    "      res = [0]*len(nums)\n",
    "      for i in range(len(nums)):\n",
    "        res[i] = pre_dif[i] - suf_dif[i]\n",
    "      return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        s = set()\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            s.add(nums[i])\n",
    "            suf[i] = len(s)\n",
    "\n",
    "        s.clear()\n",
    "        ans = [0] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            s.add(x)\n",
    "            ans[i] = len(s) - suf[i + 1]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        for i in range(len(nums)):\n",
    "            ans.append(len(set(nums[: i + 1])) - len(set(nums[i + 1 :])))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        s = set()\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            s.add(nums[i])\n",
    "            suf[i] = len(s)\n",
    "\n",
    "        s.clear()\n",
    "        ans = [0] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            s.add(x)\n",
    "            ans[i] = len(s) - suf[i + 1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        n = len(nums)\n",
    "        for i,num in enumerate(nums):\n",
    "            if i+1==n:\n",
    "                ans.append(len(set(nums[:i+1])))\n",
    "            else:\n",
    "                ans.append(len(set(nums[:i+1])) - len(set(nums[i+1:])))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        front = {}\n",
    "        back = {}\n",
    "        for n in nums:\n",
    "            back[n] = back.get(n, 0) + 1\n",
    "        diff = []\n",
    "        for n in nums:\n",
    "            front[n] = front.get(n, 0)+1\n",
    "            if back[n] == 1:\n",
    "                back.pop(n)\n",
    "            else:\n",
    "                back[n] = back[n] -1\n",
    "            diff.append(len(front) - len(back))\n",
    "        return diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        s = set()\n",
    "        pre = []\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in s:\n",
    "                s.add(nums[i])\n",
    "            pre.append(len(s))\n",
    "        s.clear()\n",
    "        last = [0 for i in range(len(nums)+1)]\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            if nums[i] not in s:\n",
    "                s.add(nums[i])\n",
    "            last[i] = len(s)\n",
    "        \n",
    "        ans = [0 for i in range(len(nums))]\n",
    "        for i in range(len(ans)):\n",
    "            ans[i] = pre[i] - last[i+1]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        left, right = Counter(), Counter(nums)\n",
    "        ans = []\n",
    "        for n in nums:\n",
    "            left[n] += 1\n",
    "            right[n] -= 1\n",
    "            if right[n] == 0:\n",
    "                del(right[n])\n",
    "            ans.append(len(left) - len(right))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        ans, length = [], nums.__len__()\n",
    "        for i in range(length):\n",
    "            left = set(nums[:i+1])\n",
    "            right = set(nums[i+1:])\n",
    "            ans.append(len(left) - len(right))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        result, ct, s = [], Counter(nums), set()\n",
    "        cur = -len(ct)\n",
    "        for x in nums:\n",
    "            result.append(cur := cur + (ct[x] == 1) + (not x in s))\n",
    "            ct[x] -= s.add(x) or 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n+1)\n",
    "        s = set()\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            s.add(nums[i])\n",
    "            suf[i] = len(s)\n",
    "\n",
    "        s.clear()\n",
    "        ans = [0] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            s.add(x)\n",
    "            ans[i] = len(s) - suf[i + 1]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        s = set()\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            s.add(nums[i])\n",
    "            suf[i] = len(s)\n",
    "\n",
    "        s.clear()\n",
    "        ans = [0] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            s.add(x)\n",
    "            ans[i] = len(s) - suf[i + 1]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        result=[]\n",
    "        for i in range(len(nums)):\n",
    "            result.append(len(set(nums[0:i+1]))-len(set(nums[i+1::])))\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        firSet = set()\n",
    "        lasSet = set()\n",
    "        diff = [0 for i in range(len(nums))]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in firSet:\n",
    "                firSet.add(nums[i])\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[j] not in lasSet:\n",
    "                    lasSet.add(nums[j])\n",
    "            diff[i] = len(firSet) - len(lasSet)   \n",
    "            lasSet.clear()\n",
    "        return diff\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        result = []\n",
    "        for i in range(len(nums)):\n",
    "            result.append(len(set(nums[:i + 1])) - len(set(nums[i + 1:])))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        res = [len(set(nums[:i+1]))-len(set(nums[i+1:])) for i in range(len(nums))]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        result = []\n",
    "        for i in range(len(nums)):\n",
    "            result.append(len(set(nums[:i+1])) - len(set(nums[i+1:])))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        pre=[0]*n\n",
    "        suf=[0]*(n+1)\n",
    "        s=set()\n",
    "        for i,x in enumerate(nums):\n",
    "            s.add(x)\n",
    "            pre[i]=len(s)\n",
    "        s=set()\n",
    "        for i in range(n-1,-1,-1):\n",
    "            s.add(nums[i])\n",
    "            suf[i]=len(s)\n",
    "        return [pre[i]-suf[i+1] for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        for i in range(len(nums)):\n",
    "            res = len(set(nums[:i+1])) - len(set(nums[i+1:]))\n",
    "            ans.append(res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            ans.append(len(set(nums[:i+1])) - len(set(nums[i+1:])))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        result = []\n",
    "        for i in range(len(nums)):\n",
    "            result.append(len(set(nums[:i + 1])) - len(set(nums[i + 1:])))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        ans = list()\n",
    "        for i in range(len(nums)):\n",
    "            ans.append(len(set(nums[:i + 1])) - len(set(nums[i + 1:])))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        return [len(set(nums[:i])) - len(set(nums[i:])) for i in range(1, len(nums) + 1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: list[int]) -> list[int]:\n",
    "\n",
    "        res = []\n",
    "        for i in range(1, len(nums)):\n",
    "            res.append(len(set(nums[:i])) - len(set(nums[i:])))\n",
    "        res.append(len(set(nums)))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]: \n",
    "\n",
    "        length = len(nums) \n",
    "        diff = [0] * length \n",
    "        for i in range(length): \n",
    "            pre = set(nums[:i+1]) \n",
    "            suf = set(nums[i+1:]) \n",
    "            diff[i] = len(pre) - len(suf)\n",
    "        \n",
    "        return diff\n",
    "        \n",
    "\n",
    "        \n",
    "        ''' \n",
    "        先用set去除相同元素，在用len计算不同元素的数量。 \n",
    "        \n",
    "        作者：I2ecursing Chaum12L\n",
    "        链接：https://leetcode.cn/problems/find-the-distinct-difference-array/solutions/2267370/2670-zhao-chu-bu-tong-yuan-su-shu-mu-cha-gmhu/\n",
    "        ''' "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        c1 = Counter(nums[0:1])\n",
    "        c2 = Counter(nums[1:])\n",
    "        diff = [0] * len(nums)\n",
    "        diff[0] = len(c1) - len(c2)\n",
    "        for i, n in enumerate(nums[1:]):\n",
    "            diff[i+1] = diff[i]\n",
    "            diff[i+1] += n not in c1\n",
    "            diff[i+1] += c2[n] == 1\n",
    "            c1[n] += 1\n",
    "            c2[n] -= 1\n",
    "        return diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        ans=[]\n",
    "        for i in range(len(nums)):\n",
    "            ans.append(len(set(nums[0:i+1]))-len(set(nums[i+1:len(nums)])))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        i = 0\n",
    "        j = len(nums)-1\n",
    "        a = [0] * len(nums)\n",
    "        aa = set()\n",
    "        bb = set()\n",
    "        while i<len(nums):\n",
    "            a[j]-=len(bb)\n",
    "            aa.add(nums[i])\n",
    "            bb.add(nums[j])\n",
    "            a[i]+=len(aa)\n",
    "            i+=1\n",
    "            j-=1\n",
    "        return a\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [0] * n\n",
    "        for i in range(n):\n",
    "            if i < n - 1:\n",
    "                res[i] = len(set(nums[:i + 1])) - len(set(nums[i + 1:]))\n",
    "            else:\n",
    "                res[i] = len(set(nums[:i + 1]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        suffix = [0] * (n+1)\n",
    "        s = set()\n",
    "        for i in range(n-1, -1, -1):\n",
    "            s.add(nums[i])\n",
    "            suffix[i] = len(s)\n",
    "        \n",
    "        ans = []\n",
    "        s = set()\n",
    "        for i in range(n):\n",
    "            s.add(nums[i])\n",
    "            ans.append(len(s) - suffix[i+1])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        return [len(set(nums[:i+1])) - len(set(nums[i+1:])) for i in range(len(nums))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        s = set()\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            s.add(nums[i])\n",
    "            suf[i] = len(s)\n",
    "        s.clear()\n",
    "        ans = [0] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            s.add(x)\n",
    "            ans[i] = len(s) - suf[i + 1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        cnt1 = Counter(nums)\n",
    "        cnt2 = {}\n",
    "        for num in nums:\n",
    "            if num not in cnt2:\n",
    "                cnt2[num] = 1\n",
    "            if num in cnt1:\n",
    "                cnt1[num] -= 1\n",
    "            if cnt1[num] <= 0:\n",
    "                del cnt1[num]\n",
    "            ans.append(len(cnt2.keys())-len(cnt1.keys()))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        left, right = Counter(), Counter(nums)\n",
    "        res = []\n",
    "        for i in nums:\n",
    "            left[i] += 1\n",
    "            right[i] -= 1\n",
    "            if right[i] == 0:\n",
    "                del right[i]\n",
    "            res.append(len(left)-len(right))\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        prefix = [1] * (n + 1)\n",
    "        suffix = [1] * (n + 2)\n",
    "        s1 = set()\n",
    "        s2 = set()\n",
    "        for i in range(1, n+1):\n",
    "            if nums[i-1] not in s1:\n",
    "                s1.add(nums[i-1])\n",
    "                prefix[i] = prefix[i-1] + 1\n",
    "            else:\n",
    "                prefix[i] = prefix[i-1]\n",
    "        \n",
    "        for i in range(n, 0, -1):\n",
    "            if nums[i-1] not in s2:\n",
    "                s2.add(nums[i-1])\n",
    "                suffix[i] = suffix[i+1] + 1\n",
    "            else:\n",
    "                suffix[i] = suffix[i+1]\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(1, n+1):\n",
    "            a = prefix[i]\n",
    "            b = suffix[i+1]\n",
    "            ans.append(a - b)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        s = set()\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            s.add(nums[i])\n",
    "            suf[i] = len(s)\n",
    "\n",
    "        s.clear()\n",
    "        ans = [0] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            s.add(x)\n",
    "            ans[i] = len(s) - suf[i + 1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        s=set()\n",
    "        n=len(nums)\n",
    "        pre=[0]*n\n",
    "        suf=[0]*(n+1)\n",
    "        for i,x in enumerate(nums) :\n",
    "            s.add(x)\n",
    "            pre[i]=len(s)\n",
    "        s.clear()\n",
    "        for i in range(n-1,0,-1) :\n",
    "            s.add(nums[i])\n",
    "            suf[i]=len(s)\n",
    "        ans=[]\n",
    "        for i in range(n) :\n",
    "            ans.append(pre[i]-suf[i+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        s = set()\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            s.add(nums[i])\n",
    "            suf[i] = len(s)\n",
    "\n",
    "        s.clear()\n",
    "        ans = [0] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            s.add(x)\n",
    "            ans[i] = len(s) - suf[i + 1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [0] * n\n",
    "        for i in range(n):\n",
    "            res[i] = len(set(nums[:i+1]))\n",
    "        for i in range(n-2, -1, -1):\n",
    "            res[i] = res[i] - len(set(nums[i+1:]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        c =[]\n",
    "        n = len(nums)\n",
    "        for i in range(1,len(nums)+1):\n",
    "            b = len(set(nums[0:i]))-len(set(nums[i:n]))\n",
    "            c.append(b)\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        h = Counter(nums)\n",
    "        pre, suf = 0, len(h)\n",
    "        st = set()\n",
    "        res = []\n",
    "        for v in nums:\n",
    "            h[v] -= 1\n",
    "            if h[v] == 0:\n",
    "                suf -= 1\n",
    "            if v not in st:\n",
    "                pre += 1\n",
    "            st.add(v)\n",
    "            res.append(pre - suf)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        st = set()\n",
    "        sufCnt = [0] * (len(nums) + 1)\n",
    "        for i in range(len(nums) - 1, 0, -1):\n",
    "            st.add(nums[i])\n",
    "            sufCnt[i] = len(st)\n",
    "        res = []\n",
    "        st.clear()\n",
    "        for i in range(len(nums)):\n",
    "            st.add(nums[i])\n",
    "            res.append(len(st) - sufCnt[i + 1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        ans=[]\n",
    "        for idx in range(len(nums)):\n",
    "            ans.append(len(set(nums[:idx+1]))-len(set(nums[idx+1:])))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int] :\n",
    "        n = len(nums)\n",
    "        diff = []\n",
    "        for i in range(n) :\n",
    "            diff.append(len(set(nums[:i+1:])) - len(set(nums[i+1::])))\n",
    "        return diff\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        diff = [0*i for i in range(len(nums))]\n",
    "        for i in range(len(nums)):\n",
    "            nums_left = nums[:i+1]\n",
    "            nums_right = nums[i+1:]\n",
    "            nums_left_count = len(list(set(nums_left)))\n",
    "            nums_right_count = len(list(set(nums_right)))\n",
    "            diff[i] = nums_left_count - nums_right_count\n",
    "        return diff "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        cnt=Counter(nums)\n",
    "        vis=set()\n",
    "        ans=[]\n",
    "        for num in nums:\n",
    "            vis.add(num)\n",
    "            cnt[num]-=1\n",
    "            if cnt[num]==0:\n",
    "                del cnt[num]\n",
    "            ans.append(len(vis)-len(cnt))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n",
    "        return [len(set(nums[:i+1]))-len(set(nums[i+1:])) for i in range(len(nums))]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
